SP7001 VLATTICE - Visible Lattice Points

---

简单的莫比乌斯反演题

---

题解：

首先这道题有个众所周知的可以用欧拉函数水过的二维版本P2158仪仗队

先摆出二维版本的简单解析：

初步分析：答案分成“两个坐标轴”和“一个面”两部分
（那个常数2和3是坐标轴的贡献，下同）

$$ans=2+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=1]$$

设：

$$f(x)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=x]$$ $$g(x)=\sum\limits_{x\mid y}f(y)=\left \lfloor \frac{n}{x} \right \rfloor^{2}$$

根据莫比乌斯反演：

$$f(x)=\sum\limits_{x\mid y}\mu (\left \lfloor \frac{y}{x} \right \rfloor)\cdot g(y)=\sum\limits_{x\mid y}\mu (\left \lfloor \frac{y}{x} \right \rfloor)\cdot \left \lfloor \frac{n}{y} \right \rfloor^{2}$$

所以答案就是：

$$ans=2+f(1)=2+\sum\limits_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor^{2}$$

---

再来看三维的情况，基本相同，只是答案由“三个坐标轴”，“三个面”和“一个体”组成:

$$ans=3+3*p+\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}[\gcd(i,j,k)=1]$$

其中$p$是一个面上的贡献，上面已经算出，即$p=\sum\limits_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor^{2}$，我们先放着不管，只考虑后半部分

（与二维几乎一模一样）设：

$$f(x)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=1}^{n}[\gcd(i,j,k)=x]$$ $$g(x)=\sum\limits_{x\mid y}f(y)=\left \lfloor \frac{n}{x} \right \rfloor^{3}$$

根据莫比乌斯反演：

$$f(x)=\sum\limits_{x\mid y}\mu (\left \lfloor \frac{y}{x} \right \rfloor)\cdot g(y)=\sum\limits_{x\mid y}\mu (\left \lfloor \frac{y}{x} \right \rfloor)\cdot \left \lfloor \frac{n}{y} \right \rfloor^{3}$$

（好像只改了个指数呢）所以答案就是：

$$ans=3+3*p+f(1)$$ $$ans=3+3*\sum\limits_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor^{2}+\sum\limits_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor^{3}$$ $$ans=3+\sum\limits_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor^{2}\cdot (3+\left \lfloor \frac{n}{i} \right \rfloor)$$

照着答案式子打，我们便得到了复杂度$O(tn)$的代码：

    ans=3;
    for(int i=1;i<=n;i++)
        ans+=mu[i]*(pow(n/i,3)+3*pow(n/i,2));

接着注意到答案的式子还可以经典地整除分块一下，记个$\mu$的前缀和，接着便有了下面的代码，复杂度降为$O(t\sqrt{n})$：

---

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=1e6+5;
bool v[N];
int p[N],pn,mu[N],pre[N];

void muin(int n){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!v[i]){
            p[++pn]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=pn&&p[j]*i<=n;j++){
            v[i*p[j]]=1;
            if(i%p[j]) mu[i*p[j]]=-mu[i];
            else{
                mu[i*p[j]]=0;
                break;
            }
        }
    }
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+mu[i]; //前缀和
}

void doit(){
    int n;
    long long ans=0;
    read(n);
    for(int l=1,r;l<=n;l=r+1){
        r=n/(n/l); //块的左右边界
        ans+=1ll*(pre[r]-pre[l-1])*((n/l)+3)*(n/l)*(n/l); //代入公式
    }
    write(ans+3);puts(""); //最后的坐标轴贡献
}

signed main(){
    muin(1e6);
    int t;
    read(t);
    while(t--) doit();
}